package gold.digger;

import gold.utils.InputUtil;
import gold.vo.CodeDoc;

/**
 * Created by fanzhenyu02 on 2020/6/27.
 * common problem solver template.
 */
public class LC287 {
    public long startExecuteTime = System.currentTimeMillis();

    /*
     * @param 此题目直接用别人代码，自己只理解思想
     * 经典解法，每日一看
     * 把重复数组问题转换为链表存在环的问题
     * @return:
     */
    public int findDuplicate(int[] arr) {
        int slow = arr[0], fast = arr[arr[0]];
        while (slow != fast) {
            slow = arr[slow];
            fast = arr[arr[fast]];
        }

        int pre = 0;
        while (pre != slow) {
            pre = arr[pre];
            slow = arr[slow];
        }

        return pre;
    }

    ////    链接：https://leetcode-cn.com/problems/find-the-duplicate-number/solution/by-longluo-e315/
    ////    标记法的思想和计数法是一致的，但这个方法比计数法，Set更为巧妙。
    ////    考虑到数组元素值的范围是[1, n][1,n]，但数组长度为n + 1n+1，那么很显然在遍历数组的时候，我们将数组的值变为其对应的负数，那么再次遇到负数就得到了答案。
    public static int findDuplicate_mark(int[] nums) {
        int len = nums.length;
        for (int num : nums) {
            int idx = Math.abs(num);
            if (nums[idx] < 0) {
                return idx;
            }
            nums[idx] = -nums[idx];
        }

        return len;
    }

    public static void main(String[] args) throws Exception {
        LC287 an = new LC287();
        int[] arr = {1, 2, 2, 2, 3};
        System.out.println(an.findDuplicate(arr));


        InputUtil.run();
        CodeDoc.run();
        System.out.println("\nanswer total execute time: " + (System.currentTimeMillis() - an.startExecuteTime) + " ms.");
    }
}
